第51章 哈夫曼树

哈夫曼树(Huffman Tree)又称最优二叉树，是一种带权路径长度最短的二叉树，由计算机科学家大卫哈夫曼于1952年提出。哈夫曼树在数据压缩、决策系统等领域有着广泛应用。

51.1 哈夫曼树的基本概念

51.1.1 核心术语

权值：赋予树中点的一个有意义的数值(如频率、概率、代价等)。 路径长度：从树中一个节点到另一个节点所经过的边的数量。 节点的带权路径长度：从根节点到该节点的路径长度与该节点权值的乘积。 树的带权路径长度(WPL)：树中所有叶子节点的带权路径长度之和，计算公式为

$$W=\sum_{i=1}^{n} w_{i} \times d_{i}$$

其中$w_{i}$为第$i$个叶子节点的权值，$d_{i}$为根节点到第$i$个叶子节点的路径长度，$n$为叶子节点总数。

51.1.2 哈夫曼树的定义

哈夫曼树是指对于给定的$n$个带权值的叶子节点，所能构造出的带权路径长度最小的二叉树。

示例： 假设有4个叶子节点，权值分别为3、4、5、6。 树A构造方式：根左子树为3，右子树为权值4的子树，该子树右分支包含5、6。

$$W=3 \times 1+4 \times 2+5 \times 3+6 \times 3=3+8+15+18=44$$

树B为哈夫曼树：

$$W=3 \times 3+4 \times 3+5 \times 2+6 \times 2=9+12+10+12=43$$

对比可见树B的带权路径更小，是对应哈夫曼树。

51.2 哈夫曼树的构造方法

哈夫曼树构造属于贪心算法，核心思路：每次选取权值最小的两棵树合并，直到仅剩一棵树。 步骤：

1. 初始化：所有叶子节点各自独立形成森林。
2. 选取合并：从森林取出权值最小两棵树，创建新父节点，权值为两棵树根权值之和，两棵树作为新节点左右子树。
3. 更新森林：移除原来两棵树，将新树加入森林。
4. 循环重复，森林只剩一棵树时构造完成。

示例：权值3、4、5、6构造流程 步骤1：森林集合6 步骤2：合并3与4，新节点权值7，森林7 步骤3：合并5与6，新节点权值11，森林11 步骤4：合并7与11，根节点权值18，构造完成。 最终带权路径$W=3 \times 3+4 \times 3+5 \times 2+6 \times 2=43$。

51.2.1 数据结构选择

构造过程需要频繁取出最小权值节点，优先使用最小堆（优先队列）提升效率。

#include <queue>
#include <vector>
using namespace std;
//哈夫曼树节点结构
struct HuffmanNode {
    int weight;
    HuffmanNode *left;
    HuffmanNode *right;
    HuffmanNode (int w): weight (w), left (NULL), right (NULL) {}
};
//最小堆比较器
struct CompareNode {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->weight > b->weight;
    }
};

51.2.2 构造算法实现

HuffmanNode* buildHuffmanTree(vector<int> weights){
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNode> minHeap;
    //所有权值节点入堆
    for (int w: weights){
        minHeap.push(new HuffmanNode(w));
    }
    //不断合并最小两棵树
    while (minHeap.size()>1){
        HuffmanNode *left = minHeap.top();
        minHeap.pop();
        HuffmanNode *right = minHeap.top();
        minHeap.pop();
        //创建合并父节点
        HuffmanNode *parent = new HuffmanNode(left->weight + right->weight);
        parent->left=left;
        parent->right= right;
        minHeap.push(parent);
    }
    return minHeap.top();
}

51.3 哈夫曼编码

哈夫曼编码是哈夫曼树核心应用，无损压缩算法，高频字符分配短编码，低频分配长编码，整体总编码长度最小。

51.3.1 编码规则

从根到叶子，左分支标记0、右分支标记1，路径拼接得到该字符编码。 前缀编码特性：任意字符编码不会是另一个字符编码的前缀，解码无歧义。

示例：字符权值A=3、B=4、C=5、D=6 A编码：000 B编码：001 C编码：01 D编码：1 总编码长度：

$$3 \times 3+4 \times 3+5 \times 2+6 \times 1=9+12+10+6=37$$

51.3.2 编码实现

void generateHuffmanCodes (HuffmanNode *root, string code, vector<pair<int, string>>& codes){
    if (root == NULL) return;
    //到达叶子节点，记录编码
    if (root->left == NULL && root->right == NULL){
        codes.push_back({root->weight, code});
        return;
    }
    generateHuffmanCodes(root->left, code + "0", codes);
    generateHuffmanCodes(root->right, code + "1", codes);
}

51.4 哈夫曼树的特性

1. 结构特性：哈夫曼树不存在度为1的节点，所有非叶子节点度均为2；若叶子数量为$n$，总节点数 = n + (n-1) = 2n-1$2n-1$。

$$总节点数 = n + (n-1) = 2n-1 = n + (n-1) = 2n-1$$

2. 最优性：相同叶子权值集合下，哈夫曼树WPL一定最小。
3. 不唯一性：合并时左右子树可交换、相同权值选取顺序不同，树结构可能不同，但WPL完全相等。

51.5 应用场景

1. 数据压缩：ZIP、GZIP等压缩文件核心算法，减少冗余数据。
2. 通信编码：降低传输数据量，节省带宽。
3. 决策系统：依据代价构建最优决策树。
4. 文本频率统计：根据字符频次生成最短编码。

51.6 注意事项

1. 权值为0的节点必须参与构造，否则WPL计算出错。
2. 仅单个叶子节点时，编码统一记为"0"。
3. 时间复杂度：使用最小堆构造哈夫曼树复杂度$O(n \log n)$，无序数组暴力查找为$O(n^2)$。
4. 解码流程：读取编码0/1，从根向下遍历，抵达叶子即完成一个字符解码。